在类Tool中定义一个方法 isPower,要求对于形参num(num>0),判断num是不是2的幂,如果是返回true,否则返回false 在Main类中main方法中调用此方法,输入一个大于0的整数,调用isPower方法,如果是2的幂,输出yes,否则输出no 输入如果是0或者小于0的整数,输出error
输入格式:
输入一个整数
输出格式:
输出结果
输入样例1:
输出样例1:
输入样例2:
输出样例2:
输入样例3:
输出样例3:
思路
题目可能是Java练习题,所以说类、方法什么的。。。
题意很简单,判断一个数n是不是2的幂,在纸上写下2、4、8、16等等这些数的二进制看一下
如果一个十进制数n是2的幂,那么其二进制除最高位为1,其余位均为0。根据这一点,代码复杂度为O(logn)
也可使用位运算,n&(-n)或n&(n-1),复杂度为O(1),可百度一下
知识点:十进制转二进制、两个位运算技巧
依次类推,判断一个十进制数是否是3的幂、4的幂、5的幂等等,看一看其对应的进制表示是否除最高位为1,其余位均为0即可
代码
进制转换方法,复杂度O(logn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| #include <iostream> #include <stack>
using namespace std;
bool func(int n) { stack<int> st; while(n > 0) { st.push(n % 2); n = n / 2; } string ret; int sum = 0; while(!st.empty()) { ret += st.top() + '0'; if(st.top() == 0) { sum++; } st.pop(); } return sum == (int)ret.size() - 1 && ret[0] == '1'; }
int main() { int n; cin >> n; if(n <= 0) { cout << "error" << endl; } else { cout << (func(n) ? "yes" : "no") << endl; } return 0; }
|
位运算方法,复杂度O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| #include <iostream>
using namespace std;
int main() { int n; cin >> n; if(n <= 0) { cout << "error" << endl; } else { cout << ((n & (-n)) == n ? "yes" : "no") << endl; } return 0; }
|